package Class019;

public class HandleInputAndOutput {
    public static void main(String[] args) {
        int[][] mat = {
                {1, 2, 0},
                {-3, 4, 7},
                {6, -11, 9}
        };
        System.out.println("Max mat sum:" + getMaxSubMat(mat));
    }

    //子矩阵的最大和问题
    public static int getMaxSubMat(int[][] mat) {
        int N = mat.length, M = mat[0].length;
        int ans = Integer.MIN_VALUE;
        for(int i = 0; i < N; i++) {
            int[] cur = new int[M];
            for(int j = i; j < N; j++) {
                for(int k = 0; k < M; k++) {
                    cur[k] += mat[j][k];
                }
                ans = Math.max(ans, getMaxSumArr(cur));
            }
        }
        return ans;
    }

    public static int getMaxSumArr(int[] arr) {
        int N = arr.length;
        int pre = arr[0];
        int cur = 0;
        int ans = pre;
        for(int i = 1; i < N; i++) {
            cur = arr[i] + Math.max(0, pre);
            pre = cur;
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}
